package com.whitedust.top70;

import java.util.Arrays;

/**
 *
 * @author A
 * @since 2025/11/11 12:55
 */

public class Top68 {
    int[][] dir = new int[][]{{0, 1}, {1, 0}};
    int res = Integer.MAX_VALUE;

    public int minPathSum(int[][] grid) {
        int[] dp = new int[grid[0].length + 1];

        Arrays.fill(dp, Integer.MAX_VALUE);
        //这里不能是dp[0]为0，因为这样在滚动到第二行的时候他会认为他有左边的格子
        dp[1] = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                dp[j + 1] = Math.min(dp[j], dp[j + 1]) + grid[i][j];
            }
        }
        return dp[grid[0].length];
    }

    //超时
    public void dfs(int[][] grid, int x, int y, int sum) {
        sum += grid[x][y];
        if (x == grid.length - 1 && y == grid[0].length - 1) {
            res = Math.min(res, sum);
            return;
        }
        for (int i = 0; i < 2; i++) {
            int nextX = x + dir[i][0];
            int nextY = y + dir[i][1];
            if (nextX < 0 || nextY < 0 || nextX >= grid.length || nextY >= grid[0].length) continue;
            dfs(grid, nextX, nextY, sum);
            sum -= grid[x][y];
        }
    }
}
